package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1031 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
            int n = nums.length, ans = 0;
            int[] afterFirst = getAfter(nums, firstLen), afterSecond = getAfter(nums, secondLen),
                    beforeFirst = getBefore(nums, firstLen), beforeSecond = getBefore(nums, secondLen);

            // 前first后second模式
            for (int i = firstLen - 1; i < n - secondLen; i++) {
                ans = Math.max(ans, beforeFirst[i] + afterSecond[i + 1]);
            }

            // 前second后first模式
            for (int i = secondLen - 1; i < n - firstLen; i++) {
                ans = Math.max(ans, beforeSecond[i] + afterFirst[i + 1]);
            }

            return ans;
        }

        public int[] getAfter(int[] nums, int len) {
            int n = nums.length, afterSum = 0;
            int[] after = new int[n];

            for (int i = n - 1; i >= n - len; i--) {
                afterSum += nums[i];
            }

            after[n - len] = afterSum;
            for (int i = n - len - 1; i >= 0; i--) {
                afterSum += (nums[i] - nums[i + len]);
                after[i] = after[i + 1] > afterSum ? after[i + 1] : afterSum;
            }

            return after;
        }

        public int[] getBefore(int[] nums, int len) {
            int n = nums.length, beforeSum = 0;
            int[] before = new int[n];

            for (int i = 0; i <= len - 1; i++) {
                beforeSum += nums[i];
            }

            before[len - 1] = beforeSum;
            for (int i = len; i < n; i++) {
                beforeSum += (nums[i] - nums[i - len]);
                before[i] = before[i - 1] > beforeSum ? before[i - 1] : beforeSum;
            }

            return before;
        }
    }

    public void run() {
        System.out.println(new Solution().maxSumTwoNoOverlap(InputUtil.toIntegerArray("[0,6,5,2,2,5,1,9,4]"), 1, 2));
        System.out.println(new Solution().maxSumTwoNoOverlap(InputUtil.toIntegerArray("[3,8,1,3,2,1,8,9,0]"), 3, 2));
        System.out.println(new Solution().maxSumTwoNoOverlap(InputUtil.toIntegerArray("[2,1,5,6,0,9,5,0,3,8]"), 4, 3));
    }

    public static void main(String[] args) throws Exception {
        LC1031 an = new LC1031();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
